Permutations II

Time: O(NxN!); Space: O(N); medium

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example 1:

Input: nums = [1,1,2]

Output:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

[1]:

class Solution1(object):
    """
    Time: O(N*N!)
    Space: O(N)
    """
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        result = []
        used = [False] * len(nums)
        self.permuteUniqueRecu(result, used, [], nums)
        return result

    def permuteUniqueRecu(self, result, used, cur, nums):
        if len(cur) == len(nums):
            result.append(cur + [])
            return
        for i in range(len(nums)):
            if used[i] or (i > 0 and nums[i-1] == nums[i] and not used[i-1]):
                continue
            used[i] = True
            cur.append(nums[i])
            self.permuteUniqueRecu(result, used, cur, nums)
            cur.pop()
            used[i] = False

[2]:

s = Solution1()
nums = [1,1,2]
assert s.permuteUnique(nums) == [
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

[3]:

class Solution2(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        solutions = [[]]

        for num in nums:
            next = []
            for solution in solutions:
                for i in range(len(solution) + 1):
                    candidate = solution[:i] + [num] + solution[i:]
                    if candidate not in next:
                        next.append(candidate)

            solutions = next

        return solutions

[6]:

s = Solution2()
nums = [1,1,2]
assert s.permuteUnique(nums) == [[2, 1, 1], [1, 2, 1], [1, 1, 2]]
# assert s.permuteUnique(nums) == [
#   [1,1,2],
#   [1,2,1],
#   [2,1,1]
# ]